<TITLE>prob003: quasigroup existence</TITLE>
<HR><!------------------------------------------------------------------------>
<CENTER>
<H1>prob003: quasigroup existence</H1>

<TABLE>
<TR> <TD> proposed by
     <TD ALIGN=LEFT> <A HREF="http://www.cs.york.ac.uk/~tw">
          <B>Toby Walsh</B></A> 
          <ADDRESS><a href="mailto:tw@cs.york.ac.uk">
          tw@cs.york.ac.uk</a></ADDRESS>
</TABLE>
with assistance from Kostas Stergiou and Mark Stickel. 
</CENTER>
<HR><!------------------------------------------------------------------------>
<H3> Specification </H3>

<TT>
An order m quasigroup is a Latin square of size m. That is, a m by m 
multiplication table in which each element occurs once in every row and
column. For example, 
<CENTER>
<TABLE>
<TR> 
<TD> 1 <TD> 2 <TD> 3 <TD> 4 
<TR>
<TD> 4 <TD> 1 <TD> 2 <TD> 3
<TR>
<TD> 3 <TD> 4 <TD> 1 <TD> 2
<TR>
<TD> 2 <TD> 3 <TD> 4 <TD> 1
</TABLE>
</CENTER>
is an order 4 quasigroup. A quasigroup can be specified by
a set and a binary multiplication opertor, * defined over this
set. 
<P>
Quasigroup existence problems determine
the existence or non-existence of
quasigroups of a given size with additional properties.
Certain existence problems are of sufficient interest that a
naming scheme has been invented for them.
We define two new relations, *321 and *312 by
a *321 b = c iff c*b=a and
a *312 b = c iff b*c=a. 
<P>
QG1.m problems are order m quasigroups for which 
if a*b=c*d and a *321 b = c *321 d
then a=c and b=d.
<P>
QG2.m problems are order m quasigroups for which 
if a*b=c*d and a *312 b = c *312 d
then a=c and b=d.
<P>
QG3.m problems are order m quasigroups for which 
(a*b)*(b*a) = a.
<P>
QG4.m problems are order m quasigroups for which 
(b*a)*(a*b) = a.
<P>
QG5.m problems are order m quasigroups for which 
((b*a)*b)*b = a.
<P>
QG6.m problems are order m quasigroups for which 
(a*b)*b = a*(a*b).
<P>
QG7.m problems are order m quasigroups for which 
(b*a)*b = a*(b*a).
<P> 
For each of these problems, 
we may additionally demand that the quasigroup is idempotent.
That is, a*a=a for every element a. 

</TT>


<HR><!------------------------------------------------------------------------>

<UL>

 <A HREF="../../index.html"> Back</A> to CSPLib home page.


